/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***非递归二分查找       P153                   ***/
/***C++ 实现版本    written by Daniel           ***/

#include <vector>
#include <iostream>
using std::vector;
using std::cout;
using std::endl;
/*
功能：非递归版本的二分查找
参数：vec 需要查找数组的引用，必须时有序数组  target  需要查找的值
返回值： int  查找值的下标，如未找到，返回-1
*/
int binarySearch(const vector<int>& vec, int target)
{
    int left=0;
    int right=vec.size()-1;
    while(left<=right){
        auto mid=(left+right)/2;
        if (vec[mid]==target){
            return mid;
        }
        else if (vec[mid]>target){
            right=mid-1;
        }
        else{
            left=mid+1;
        }
    }
    return -1;
}

int main()
{
    vector<int> vec({1,3,4,5,6,7,8,10});
    cout<<binarySearch(vec,7)<<endl;
    cout<<binarySearch(vec,14)<<endl;
}